﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Diagnostics;

namespace TreeTraversal
{
    class Heap<T> : BinaryTree<T> where T : IComparable
    {
        public override string Name
        {
            get { return "Heap"; }
        }

        protected List<BinaryTreeNode<T>> HeapArray = new List<BinaryTreeNode<T>>();
        public override BinaryTreeNode<T> Add(T Value)
        {
            BinaryTreeNode<T> newNode = new BinaryTreeNode<T>(Value, null);
            HeapArray.Add(newNode);

            int newIndex = HeapArray.Count - 1;
            int parentIndex = GetParentIndex(newIndex);

            if (parentIndex >= 0)
            {
                BinaryTreeNode<T> parentNode = HeapArray[parentIndex];
                newNode.Parent = parentNode;
                // link up child with parent...
                if (GetLeftChildIndex(parentIndex) == newIndex)
                {
                    parentNode.Left = newNode;
                }
                else if (GetRightChildIndex(parentIndex) == newIndex)
                {
                    parentNode.Right = newNode;
                }
                else
                {
                    Debug.Assert(false);
                }

                //int depth = (int)Math.Log(HeapArray.Count, 2);
                int counter = 1;
                BinaryTreeNode<T> lastNode = newNode;
                while (parentNode != null)
                {
                    if (parentNode.Left == lastNode)
                        parentNode.LeftDepth = counter++;
                    else if (parentNode.Right == lastNode)
                        parentNode.RightDepth = counter++;

                    lastNode = parentNode;
                    parentNode = parentNode.Parent;
                }
            }

            return newNode;
        }

        protected int GetParentIndex(int nodeIndex)
        {
            double temp = ((double)nodeIndex - 1) / 2;
            return (int)Math.Floor(temp);
        }

        protected int GetLeftChildIndex(int nodeIndex)
        {
            return (2 * nodeIndex + 1);
        }

        protected int GetRightChildIndex(int nodeIndex)
        {
            return (2 * nodeIndex + 2);
        }

        public override BinaryTreeNode<T> Root()
        {
            if (HeapArray.Count > 0)
                return HeapArray[0];

            return null;
        }
    }
}
